package com.ruoyi.project;

import com.ruoyi.project.monitor.server.domain.Sys;
import org.apache.poi.ss.formula.functions.T;

import javax.sound.midi.Soundbank;
import java.io.UnsupportedEncodingException;
import java.util.*;

public class Test {

	
	public static void main(String[] args) throws Exception {
		
		String sss=new String("鑾峰緱byte[]鍨嬬殑key".getBytes("gbk"),"utf-8");
		System.out.println(sss);

		Test t = new Test();
//		ListNode head = new ListNode(1,new ListNode(3,new ListNode(2,new ListNode(4,new ListNode(5,null)))));

		int[] arr =new int[100000];
         Random rd =new Random();
         for(int i=0;i<100000;i++){
         	arr[i] = rd.nextInt(1000000);
		 }

//		int[] arr = {2,5,1,8,4,3};
         long t1 = System.currentTimeMillis();
//			t.quickSort(arr,0,arr.length-1);
		mergeSort2(arr,arr.length);
         long t2 = System.currentTimeMillis();
		System.out.println("耗时："+(t2-t1));

		System.out.println(checkSort(arr));
//         for(int a :arr){
//			 System.out.println(a);
//		 }

		List<String> list = new ArrayList<String>();
		list.add("1");
		list.add("2");
		list.add("3");
		list.remove(1);

	}

	private int[] quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int partitionIndex = partition(arr, left, right); //划分排序、排出来基准值的位置，比它大的在右边，小的在左边，都没排序
			quickSort(arr, left, partitionIndex - 1);  //再为左边的划分排序
			quickSort(arr, partitionIndex + 1, right); //再为右边的划分排序
		}
		return arr;
	}
	private int partition(int[] arr, int left, int right) { //划分排序
		// 设定基准值（pivot）
		int pivot = left;  //基准值
		int index = pivot + 1;
		for (int i = index; i <= right; i++) {
			if (arr[i] < arr[pivot]) { //比基准值小的靠左
				swap(arr, i, index);
				index++;  // 比基准值小的个数
			}
		}
		swap(arr, pivot, index - 1); // 挪动基准值，
		return index - 1;  //基准值的位置
	}

	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}


	public static int[] sort(int[] sourceArray) throws Exception {
		// 对 arr 进行拷贝，不改变参数内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

		// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
		for (int i = 1; i < arr.length; i++) {

			int tmp = arr[i];// 记录要插入的数据
			int j = i- 1; //取前一个元素

			while (j >= 0 && tmp < arr[j]) {  // 从已经排序的序列最右边的开始比较，找到比其小的数
				arr[j+1] = arr[j ];  // 比temp大就向后移动一位
				j--;
			}
			// 存在比其小的数，插入
			arr[j+1] = tmp; // j+1是移动后空出来的位置
		}
		return arr;
	}


	//折半插入排序算法
	public static void BInsertSort(int[] array) {
		for (int i = 1; i < array.length; i++) {
			int key = array[i];
			int low = 0, high = i - 1;
			while(low <= high) {
				int mod = (low + high) / 2;
				if (key < array[mod]) {
					high = mod - 1;
				} else {
					low = mod + 1;
				}
			}
			for (int j = i-1; j >= high + 1; j--) {
				array[j+1] = array[j];
			}
			array[high + 1] = key;
		}
	}

	public static boolean checkSort(int[] arr){
		for(int i=0;i<arr.length-1;i++){
			if(arr[i]>arr[i+1]){
				return false;
			}
		}
		return true;
	}

	public static void mergeSort(int[] arr,int left,int len){
		int[] a = new int[len-left];
		int size = 1; //储存第二路元素的长度用， 提前分配空间 避免循环中反复分配， 要是开心，后边的变量都可以提前分配好空间
		for(int step=1;step<len-left; step <<= 1 ){
			 for(int i=left;i<len-step;i+=(step<<1)){
			 	size = i+step<<1 >len ? len-i-step:step;

			 }
		}
	}

	public static void mergeSort2(int[] arr,int len){
		int[] a = arr;
		int[] b = new int[len];
		int step,start;
		for(step=1;step<len; step += step ){
			for(start=0;start<len; start += step*2){
				int low = start;
				int mid = start+step >len ? len : start+step ;
				int high = start+2*step >len ? len : start+2*step;
				int k = low;
				int start1 = low, end1 = mid;
				int start2 = mid, end2 = high;
				while (start1 < end1 && start2 < end2){
					b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
				}
				while (start1 < end1){
					b[k++] = a[start1++];
				}
				while (start2 < end2){
					b[k++] = a[start2++];
				}
			}
			int[] temp = a;
			a = b;
			b = temp;
		}
		if (a != arr) {
			int i;
			for (i = 0; i < len; i++)
				b[i] = a[i];
			b = a;
		}
		b=null;
	}


	public static void add_list(List<String> list, String temp, int x, int n) {
		x++;
		if(x<=n) {
			add_list(list,temp+"(",x,n);
			add_list(list,temp+")",x,n);

		}
		if(x>n) {
			//在这里写判断条件是否负荷有效的括号组合
			char[] k=temp.toCharArray();
			//计数器
			int timer=0;
			for(int i=0;i<k.length;i++) {
				if(timer<0||timer>n/2) {
					return;
				} else {
					if(k[i]=='(') {
						timer++;
					}else {
						timer--;
					}
				}
			}
			if(timer==0){
				list.add(temp);
			}
		}
	}


}
